﻿// Sumsets POJ - 2229.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS


#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>

using namespace std;
//https://vjudge.csgrandeur.cn/problem/POJ-2229
/*
农夫约翰命令他的奶牛寻找不同的数组，这些数组的总和是一个给定的数字。奶牛只能使用 2 的整数次幂的数字。以下是总和为 7 的一组可能的数字：

1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4

帮助 FJ 计算给定整数 N 的所有可能表示（1 <= N <= 1,000,000）。
输入
一行，包含一个整数 N。
输出
将 N 表示为指定总和的方法数。由于该数字可能很大，因此只打印最后 9 位数字（以基 10 表示）。

7

6

*/

int dp[21][1000010];
int ans;
int n;

int main()
{
	scanf("%d",&n);
	for (int i = 0; i <= n; i++) {
		dp[0][i] = 1;
	}
	ans = 1;
	for (int i = 1; i <= 20; i++) {
		for (int j = 0; j <= n; j++) {
			dp[i][j] = dp[i - 1][j];
			if (j >=  (1<<i)) {
				dp[i][j] += dp[i][j - (1<<i)];
				dp[i][j] = dp[i][j] % 1000000000;
			}
		}
	}
	printf("%d\n",dp[20][n]);
	return 0;
}

 